package array

import (
	"container/heap"
)

// 最小的k个数
// 输入数组arr 找出其中最小的k个数
// 输入4 5 1 6 2 7 3 8 则最小的4个数为 1 2 3 4

func MinK(a []int, k int) []int {
	// 先排序 再返回前k个数 时间复杂度 nlogn 空间复杂度logn（排序）
	//if len(a) == 0 {
	//	return nil
	//}
	//sort.Ints(a)
	//
	//mink := make([]int, 0)
	//for i := 0; i < k && k < len(a); i++ {
	//	mink = append(mink, a[i])
	//}
	//return mink

	// 大顶堆 时间复杂度nlogk  空间复杂度 k
	if len(a) == 0 {
		return nil
	}
	d := &heapInt{}
	for _, v := range a {
		if d.Len() < k {
			heap.Push(d, v)
		} else {
			if d.Peek() > v {
				heap.Pop(d)
				heap.Push(d, v)
			}
		}
	}

	return *d
}

type heapInt []int

//Less  小于就是小跟堆，大于号就是大根堆
func (h *heapInt) Less(i, j int) bool { return (*h)[i] > (*h)[j] }
func (h *heapInt) Swap(i, j int)      { (*h)[i], (*h)[j] = (*h)[j], (*h)[i] }
func (h *heapInt) Len() int           { return len(*h) }
func (h *heapInt) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *heapInt) Pop() interface{} {
	t := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return t
}
func (h *heapInt) Peek() int {
	return (*h)[0]
}
